#include<iostream>
using namespace std;


bool is_ok(int size, int *arr, int row, int col)
{		
	int leftup = col - 1;//定义leftup表左上角
	int rightup= col + 1;//定义rightup表右上角
	
	//若为第一行，可以放
	if (row == 0)
	{
		return true;
	}

	//遍历该行情况下上面的每一行每一列,判断是否能放下皇后
	for (int i = row - 1; i >= 0; i--)
	{	
		//判断同列是否能放
		if (arr[i] == col)
		{
			return false;
		}

		//判断左上角是否能放
		if (arr[i] == leftup&&leftup>=0)
		{
			return false;
		}
		
		//判断右上角是否能放
		if (arr[i] == rightup&&rightup<size)
		{
			return false;
		}

		//遍历整个左上角，右上角
		leftup--;
		rightup++;
	}
	return true;
}

void queue(int size, int row, int &count, int* arr)
{
	//当行数等于一维数组的行数时，则说明遍历一遍完毕，方法加一
	if (size == row)
	{
		count++;
		for (int row = 0; row < size; row++)//扫描每行每列
		{
			for (int col = 0; col < size; col++)
			{
				if (arr[row] == col)//八皇后放置地方置为1，否则为0
				{
					cout << "1";
				}
				else
				{
					cout << "0";
				}
			}
			cout << endl;
		}
		cout << endl;
	}

	for (int col = 0; col < size; col++)//从第一列开始，逐个判断哪一列能够放下皇后
	{
		if (is_ok(size, arr, row, col))
		{
			arr[row] = col;			//将放皇后的位置记录下来
			queue(size, row+1, count, arr);//递归遍历剩余
		}
	}
}

int main()
{
	int size,count=0;
	cin >> size;//输入棋盘的大小
	int* arr = new int[size]();
	queue(size, 0, count, arr);
	cout <<"在"<<size<<"*"<<size<<"棋盘里八皇后放置法有"<< count <<"种方法"<< endl;

	return 0;
}